/**
 * Copyright (c) 2019, ShangHai YTO Co., Ltd.
 * All right reserved.
 * <p>
 * THIS IS UNPUBLISHED PROPRIETARY SOURCE CODE OF YTO
 * CO., LTD.  THE CONTENTS OF THIS FILE MAY NOT BE DISCLOSED
 * TO THIRD PARTIES, COPIED OR DUPLICATED IN ANY FORM, IN WHOLE OR IN PART,
 * WITHOUT THE PRIOR WRITTEN PERMISSION OF YTO
 * CO., LTD.
 */
package org.sc.xl.algorithm;

/**
 * @author FXL
 * @description: TODO 请在此添加描述
 * @reason: TODO ADD REASON(可选)
 * @date 2021/9/2 15:28
 * @since JDK 1.8
 */

class TrieNode {
    int count;
    int prefix;
    TrieNode[] nextNode = new TrieNode[26];

    public TrieNode() {
        count = 0;
        prefix = 0;
    }
}

/**
 * @author admin
 */
public class PrefixTree {


    /**
     * 新增
     *
     * @param root
     * @param str
     */
    public static void insert(TrieNode root, String str) {
        if (null == root || str.length() == 0) {
            return;
        }
        char[] chars = str.toCharArray();
        for (int i = 0; i < chars.length; i++) {
            if (root.nextNode[chars[i] - 'a'] == null) {
                root.nextNode[chars[i] - 'a'] = new TrieNode();
            }
            root = root.nextNode[chars[i] - 'a'];
            root.prefix++;
        }
        root.count++;
    }


    /**
     * 搜索
     *
     * @param root
     * @param search
     * @return
     */
    public static int search(TrieNode root, String search) {
        if (root == null || search.length() == 0) {
            return -1;
        }
        char[] chars = search.toCharArray();
        for (int i = 0; i < chars.length; i++) {
            if (root.nextNode[chars[i] - 'a'] == null) {
                return -1;
            }
            root = root.nextNode[chars[i] - 'a'];
        }
        if (root.count == 0) {
            return -1;
        }
        return root.count;
    }


    public static void main(String[] args) {
        TrieNode trieNode = new TrieNode();
        PrefixTree.insert(trieNode, "abzdfe");
        int position = PrefixTree.search(trieNode , "abzdfe");
        System.err.println(position);
    }


}
